We introduce an extension of Dual Dynamic Programming (DDP) to solve lineardynamic programming equations. We call this extension IDDP-LP which applies tosituations where some or all primal and dual subproblems to be solved along theiterations of the method are solved with a bounded error (inexactly). Weprovide convergence theorems both in the case when errors are bounded and forasymptotically vanishing errors. We extend the analysis to stochastic lineardynamic programming equations, introducing Inexact Stochastic Dual DynamicProgramming for linear programs (ISDDP-LP), an inexact variant of SDDP appliedto linear programs corresponding to the situation where some or all problems tobe solved in the forward and backward passes of SDDP are solved approximately.We also provide convergence theorems for ISDDP-LP for bounded andasymptotically vanishing errors. Finally, we present the results of numericalexperiments comparing SDDP and ISSDP-LP on a portfolio problem with directtransation costs modelled as a multistage stochastic linear optimizationproblem. On these experiments, for some values of the noises, ISDDP-LP canconverge significantly quicker than SDDP.
展开▼
